题目大意
我们定义一个字符串$s$为$\texttt{tandem}$当且仅当这个字符串能被表示三个相同的字符串$A$首尾相连的结果
对于一个字符串$s$的所有子串$s_{l \cdots r}$，如果它是一个$\texttt{tandem}$，则它是一个有趣的$\texttt{tandem}$当且仅当$s_l \not= s_{r+1}$，否则这就是一个无聊的$\texttt{tandem}$
现在，你需要统计有趣的和无聊的$\texttt{tandem}$的数量
分析
$O(n^3)$方法
不说了，大家都会
$O(n^2)$方法
我们枚举$A$的长度$L \in [1, \frac{n}{3}]$， 并统计所有长度为$3L$的$\texttt{tandem}$
我们考虑所有下标能被$L$整除的位置，即$s_0, s_L, s_{2L}, \cdots$，不难发现对于每一个长度为$3L$的$\texttt{tandem}$都会恰好覆盖这些位置中的连续$3$个，我们设这连续三个位置为$(i, j, k)$
不难发现这些子串的起始位置$a \in [i - L + 1, i]$， 如果这个子串是一个$\texttt{tandem}$， 则有$s_{[a, a+L-1]}=s_{[a+L, a+2L-1]}=s_{[a+2L, a+3L-1]}$
由于$a \in [i - L + 1, i]$，所以我们有$a \leq i \leq a + L - 1$, $a + L \leq j \leq a + 2L - 1$, $a + 2L \leq k \leq a + 3L - 1$，所以我们可以把上述条件转化为如下条件：
上面两个条件可以表示为：子串$s[0,i],\;s[0,j],\;s[0,k]$有一个长度为$i-a+1$的相同后缀，子串$s[i,n-1],\;s[j,n-1],\;s[k,n-1]$有一个长度为$a+L-i$的相同前缀。
设$\texttt{LCP(i,j,k)}$表示$s[i,n-1],\;s[j,n-1],\;s[k,n-1]$的后缀长度，$\texttt{LCS(i,j,k)}$表示$s[0,i],\;s[0,j],\;s[0,k]$的后缀长度，则有$\max( i−LCS(i , j , k )+1, i − L +1)≤ a ≤ \min( LCP ( i , j , k )− L + i , i )$
合法的$a$共有$\min(0,\min(LCP(i,j,k)−L+i,i)−\max(i−LCS(i,j,k)+1,i−L+1)+1)$个
化简一下得到$\min(LCP(i,j,k),L)+\min(LCS(i,j,k),L)−1$，我们设这个值为$V$
可以发现:
当$V < L$时不存在$\texttt{tandem}$
当$V \ge L$时存在$V-L+1$个$\texttt{tandem}$，此时：
- 如果$LCP \le L$，则存在$1$个有趣的$\texttt{tandem}$
- 否则不存在有趣的$\texttt{tandem}$。
如果朴素的去求$\texttt{LCP,LCS}$的话，时间复杂度$\mathcal{O}(n^2)$
正解方法
可以使用字符串哈希，后缀数组$+$线段树，后缀数组$+$$\texttt{ST}$表的方法优化求$\texttt{LCP,LCS}$的过程。
总时间复杂度$\mathcal{O}(n \; \log^2 n)$或$\mathcal{O}(n \; \log n)$（取决于写法）